package mid;

/**
 *
 描述
 将给定的单链表\ L L： L_0→L_1→…→L_{n-1}→L_ nL0→L1→…→Ln−1→Ln
 重新排序为：L_0→L_n →L_1→L_{n-1}→L_2→L_{n-2}→…L0→Ln→L1→Ln−1→L2→Ln−2→…
 要求使用原地算法，不能只改变节点内部的值，需要对实际的节点进行交换。

 数据范围：链表长度 0 \le n \le 200000≤n≤20000 ，链表中每个节点的值满足 0 \le val \le 10000≤val≤1000

 要求：空间复杂度 O(n)O(n) 并在链表上进行操作而不新建链表，时间复杂度 O(n)O(n)
 进阶：空间复杂度 O(1)O(1) ， 时间复杂度 O(n)O(n)
 示例1
 输入：
 {1,2,3,4}
 返回值：
 {1,4,2,3}
 说明：
 给定head链表1->2->3->4, 重新排列为 1->4->2->3,会取head链表里面的值打印输出 1
 示例2
 输入：
 {1,2,3,4,5}
 返回值：
 {1,5,2,4,3}
 说明：
 给定head链表1->2->3->4->5, 重新排列为 1->5>2->4->3,会取head链表里面的值打印输出
 * @author WangZhiJian
 * @since 2022/1/16 0016
 */
public class 重排链表 {
    public static void reorderList(ListNode head) {
        if(head == null || head.next == null)
            return;
        // 快慢指针找中点
        ListNode slowNode = head;
        ListNode quick = head.next;
        while (quick != null){
            slowNode = slowNode.next;
            quick = quick.next;
            if(quick != null)
                quick = quick.next;
        }

        // 反旋转后部链表
        ListNode slowNodeNext = slowNode.next;
        slowNode.next = null;
        while (slowNodeNext != null){
            ListNode slowNodeNextNext = slowNodeNext.next;
            slowNodeNext.next = slowNode;
            slowNode = slowNodeNext;
            slowNodeNext = slowNodeNextNext;
        }
        ListNode first = head;
        ListNode last = slowNode;
        // 一齐回头做互换
        while (first.next != last && first != last){
            ListNode fNext = first.next;
            ListNode lNext = last.next;
            first.next = last;
            last.next = fNext;
            last = lNext;
            first = fNext;
        }
    }

    public static void main(String[] args) {
        int n = 7;
        ListNode[] nodes = new ListNode[n];
        for (int i = 0; i < n; i++) {
            ListNode ni = new ListNode(i+1);
            nodes[i] = ni;
            if(i > 0)
                nodes[i-1].next = ni;
        }
        ListNode printNode = nodes[0];
        while (printNode != null){
            System.out.print("-->"+printNode.val);
            printNode = printNode.next;
        }
        System.out.println();
        reorderList(nodes[0]);

        printNode = nodes[0];
        while (printNode != null){
            System.out.print("-->"+printNode.val);
            printNode = printNode.next;
        }
        System.out.println();

    }
}
